/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  let arr = new Array(10000).fill(0);

  for (let i = 0; i < inorder.length; i++) {
    arr[inorder[i]] = i;
  }

  function dfs(preorder, inorder, pl, pr, il, ir) {
    if (pl > pr) {
      return null;
    }

    let root = new TreeNode(preorder[pl]);

    let mid = arr[preorder[pl]];

    let midleft = mid - il;

    root.left = dfs(preorder, inorder, pl + 1, pl + midleft, il, mid - 1);

    root.right = dfs(preorder, inorder, pl + midleft + 1, pr, mid + 1, ir);

    return root;
  }

  return dfs(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
};
